#include <bits/stdc++.h>

using namespace std;

#define in read()

const int MAXN = 2e5+10;

struct aam{
	int o,x,y,k;
}s[MAXN],lst[MAXN],rst[MAXN];

int tr[MAXN],n,m,ans[MAXN],all,maxx;

void add(int x,int y){for(;x <= n;x+=x&-x) tr[x] += y;}

int query(int x){int res = 0;for(;x;x-=x&-x) res += tr[x];return res;}

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1) + (x<<3) + (ch ^ 48);
	return x * sgn;
}

void solve(int ls,int rs,int lval,int rval){
	if(lval > rval || ls > rs) return;
	if(lval == rval){
		for(int i = ls;i <= rs;i++) if(s[i].o) ans[s[i].o] = lval;
		return;
	}
	int mid = lval + rval >> 1;
	int lnum = 0,rnum = 0;
	for(int i = ls;i <= rs;i++){
		if(s[i].o){
			int tot = query(s[i].y) - query(s[i].x-1);
			if(s[i].k <= tot) lst[++lnum] = s[i];
			else s[i].k -= tot,rst[++rnum] = s[i];
		}
		else{
			if(s[i].k <= mid) add(s[i].x,1),lst[++lnum] = s[i];
			else rst[++rnum] = s[i];
		}
	}
	for(int i = ls;i <= rs;i++) if(!s[i].o && s[i].k <= mid) add(s[i].x,-1);
	for(int i = 1;i <= lnum;i++) s[ls + i - 1] = lst[i];
	for(int i = 1;i <= rnum;i++) s[ls + lnum + i - 1] = rst[i];
	solve(ls,ls + lnum - 1,lval,mid);
	solve(ls + lnum,rs,mid+1,rval);
}
			
int main(){
	n = in,m = in;
	for(int i = 1;i <= n;i++) s[++all] = (aam){0,i,0,in};
	for(int i = 1;i <= m;i++) s[++all] = (aam){i,in,in,in};
	solve(1,all,-1e9,1e9);
	for(int i = 1;i <= m;i++) printf("%d\n",ans[i]);
	return 0;
}
